package pers.lance.exercise.first;

public class MySort {

    /***
     * 冒泡排序
     * @param array
     */
    public void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    /***
     * 选择排序
     * @param array
     */
    public void selectionSort(int[] array){
        for(int i = 0; i < array.length - 1; i++) {// 做第i趟排序
            int min = i;
            for(int j = min + 1; j < array.length; j++){// 选最小的记录
                if(array[j] < array[min]){
                    min = j; //记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if(i != min){  //交换a[i]和a[min]
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
    }

    /**
     * 二分查找
     * @param key
     * @param array
     * @return
     */
    public int binarySearch(int key, int[] array){
        int len = array.length;
        int l = 0;
        int r = len - 1;
        while(l <= r){
            int mid = (l + r) / 2 ;
            if(key == array[mid]){
                return mid;
            }
            if(key > array[mid]){
                l = mid + 1;
            }
            if(key < array[mid]){
                r = mid - 1;
            }
        }
        return -1;
    }

}
